package com.by.linkedlist;

/**
 * @version 1.0
 * @Author 彭彦彬
 * @Date 2025/4/9 17:51
 * @注释
 */
public class MyLinkedList<E> {
    private Node<E> head; // 头节点
    private Node<E> tail; // 尾节点
    private int size; // 当前链表大小

    // 内部类：表示链表中的节点
    private static class Node<E> {
        E data; // 节点存储的数据
        Node<E> prev; // 指向前一个节点
        Node<E> next; // 指向下一个节点

        Node(E data, Node<E> prev, Node<E> next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    /**
     * 构造函数：初始化链表
     */
    public MyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 获取链表大小
     */
    public int size() {
        return size;
    }

    /**
     * 判断链表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 添加元素到链表末尾
     */
    public void add(E element) {
        Node<E> newNode = new Node<>(element, tail, null);
        if (tail == null) { // 如果链表为空
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        size++;
    }

    /**
     * 在指定索引处插入元素
     */
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        if (index == size) { // 如果索引等于链表大小，则添加到末尾
            add(element);
            return;
        }

        Node<E> current = getNode(index); // 找到指定索引的节点
        Node<E> newNode = new Node<>(element, current.prev, current);

        if (current.prev != null) {
            current.prev.next = newNode;
        } else { // 如果插入的是第一个节点
            head = newNode;
        }
        current.prev = newNode;
        size++;
    }

    /**
     * 获取指定索引处的元素
     */
    public E get(int index) {
        return getNode(index).data;
    }

    /**
     * 删除指定索引处的元素
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        Node<E> nodeToRemove = getNode(index); // 找到要删除的节点
        return removeNode(nodeToRemove);
    }

    /**
     * 删除指定节点
     */
    private E removeNode(Node<E> node) {
        E removedData = node.data;

        if (node.prev != null) {
            node.prev.next = node.next;
        } else { // 如果删除的是头节点
            head = node.next;
        }

        if (node.next != null) {
            node.next.prev = node.prev;
        } else { // 如果删除的是尾节点
            tail = node.prev;
        }

        node.data = null; // 清空数据
        node.prev = null;
        node.next = null;
        size--;

        return removedData;
    }

    /**
     * 获取指定索引处的节点
     */
    private Node<E> getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        Node<E> current;
        if (index < size / 2) { // 从头开始遍历
            current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else { // 从尾开始遍历
            current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
        }
        return current;
    }

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.add(10);
        list.add(20);
        list.add(30);

        System.out.println("Size: " + list.size()); // 输出 3
        System.out.println("Element at index 1: " + list.get(1)); // 输出 20

        list.remove(1);
        System.out.println("After removing element at index 1, size: " + list.size()); // 输出 2
        System.out.println("New element at index 1: " + list.get(1)); // 输出 30
    }
}